#include <iostream>
#include <vector>
#include <algorithm> // For std::min

const long long INF = 1e18; // A large value for infinity

int u_mat[4001][4001];         // Input unfamiliarity matrix
long long val_prefix[4001][4001]; // For 2D prefix sums of u_mat
long long W_cost[4001][4001];   // W_cost[i][j] = cost of people i..j in one gondola
long long dp[801][4001];    // dp[g][i] = min cost for first i people using g gondolas

// Computes dp[g][i] for i in [i_L, i_R]
// Optimal split point p (count of people in first g-1 groups) for dp[g][i] is in [p_L, p_R]
void compute(int g, int i_L, int i_R, int p_L, int p_R) {
    if (i_L > i_R) {
        return;
    }

    int i_mid = i_L + (i_R - i_L) / 2;
    long long min_val_for_imid = INF;
    int best_p_for_imid = -1;

    // Determine search range for p for dp[g][i_mid]
    // p is the count of people (0 to p-1) in the first g-1 gondolas.
    // The current (g-th) gondola takes people p to i_mid-1.
    // Min people for g-1 gondolas is g-1. So p >= g-1.
    // The g-th gondola must have at least one person: p <= i_mid-1.
    int search_p_start = std::max(g - 1, p_L);
    int search_p_end = std::min(i_mid - 1, p_R);
    
    for (int p = search_p_start; p <= search_p_end; ++p) {
        if (dp[g - 1][p] == INF) { // Cannot form previous state
            continue; 
        }
        // W_cost[p][i_mid-1] is cost for people p to i_mid-1 in one gondola
        long long current_total_cost = dp[g - 1][p] + W_cost[p][i_mid - 1];
        if (current_total_cost < min_val_for_imid) {
            min_val_for_imid = current_total_cost;
            best_p_for_imid = p;
        }
    }
    dp[g][i_mid] = min_val_for_imid;

    // Recursively solve for left and right parts
    // If no valid p was found for i_mid (best_p_for_imid = -1),
    // dp[g][i_mid] will be INF.
    // The ranges for p in recursive calls are constrained by best_p_for_imid.
    if (best_p_for_imid != -1) { // A valid transition was found
        compute(g, i_L, i_mid - 1, p_L, best_p_for_imid);
        compute(g, i_mid + 1, i_R, best_p_for_imid, p_R);
    } else { 
        // If dp[g][i_mid] is INF, it's unlikely its "children" will be better,
        // but the structure of D&C opt expects to pass original bounds if opt not found.
        // However, if no best_p, means no valid way to reach i_mid.
        // The search ranges in recursive calls will likely become empty quickly.
        // For safety, pass the original p_L, p_R (or actual search_p_start/end).
        // The original Knuth opt passes current best_p.
        // If min_val_for_imid remained INF, best_p_for_imid is -1.
        // Pass p_L, actual_p_R for left and actual_p_L, p_R for right if best_p is -1.
        // Or, simply using best_p_for_imid even if -1 works because it restricts
        // search ranges properly in children making them invalid.
        compute(g, i_L, i_mid - 1, p_L, (best_p_for_imid == -1 ? actual_p_R : best_p_for_imid));
        compute(g, i_mid + 1, i_R, (best_p_for_imid == -1 ? actual_p_L : best_p_for_imid), p_R);
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int n, k_gondolas; // Renamed k to k_gondolas to avoid conflict
    std::cin >> n >> k_gondolas;

    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            std::cin >> u_mat[i][j];
        }
    }

    // Precompute 2D prefix sums for u_mat (val_prefix)
    // val_prefix[r][c] = sum of u_mat[x][y] for 0<=x<=r, 0<=y<=c
    for (int i = 0; i < n; ++i) {
        for (int j = 0; j < n; ++j) {
            val_prefix[i][j] = u_mat[i][j];
            if (i > 0) val_prefix[i][j] += val_prefix[i - 1][j];
            if (j > 0) val_prefix[i][j] += val_prefix[i][j - 1];
            if (i > 0 && j > 0) val_prefix[i][j] -= val_prefix[i - 1][j - 1];
        }
    }

    // Precompute W_cost[i][j] = cost of putting people i..j (0-indexed) in one gondola
    // W_cost[i][j] = (sum of u_mat[x][y] for i<=x<=j, i<=y<=j, with x != y) / 2
    // Since u_mat[x][x] = 0, this is (sum of u_mat[x][y] for i<=x<=j, i<=y<=j) / 2
    for (int i = 0; i < n; ++i) {
        for (int j = i; j < n; ++j) {
            if (i == j) {
                W_cost[i][j] = 0; // One person, cost 0
            } else {
                long long sum_rect = val_prefix[j][j];
                if (i > 0) {
                    sum_rect -= val_prefix[i - 1][j];
                    sum_rect -= val_prefix[j][i - 1];
                    sum_rect += val_prefix[i - 1][i - 1];
                }
                W_cost[i][j] = sum_rect / 2;
            }
        }
    }
    
    // Initialize DP table
    // dp[g][i] is min cost for first i people (persons 0..i-1) using g gondolas
    for (int g = 0; g <= k_gondolas; ++g) {
        for (int i = 0; i <= n; ++i) {
            dp[g][i] = INF;
        }
    }
    dp[0][0] = 0; // 0 people in 0 gondolas, cost 0

    // Fill DP table
    for (int g = 1; g <= k_gondolas; ++g) {
        // To calculate dp[g][i] for i from g to n.
        // The previous state dp[g-1][p] uses p people, so p from g-1 to n-1.
        compute(g, g, n, g - 1, n - 1);
    }

    std::cout << dp[k_gondolas][n] << std::endl;

    return 0;
}